The present invention generally relates to an area filling device, and particularly to an area filling device which receives coordinate data related to endpoints of edges forming a closed loop figure and generates image data for filling the internal area of the closed loop figure.
A method of filling the internal area of a polygon has been proposed in Y. Ohno, "Scan Conversion for a polygon", PIXEL, Jan. 1984, pp.136-141. The proposed method fills the area with black pixel data as follows.
(1) Each edge of a polygon is referred to. If an edge of concern is a horizontal edge, this is neglected. Alternatively, if the edge is not a horizontal edge, the lower endpoint of the edge which has a Y coordinate value smaller than that of the other edge thereof, is referred to. Then, all the edges of the polygon of concern are arranged in the increasing order of Y coordinate values from the smallest one of the Y coordinate values. Thereby, an edge table which indicates the arrangement of edges is created. The procedure for arranging edges is based on bucket sorting.
Next, an active-edge table is created and revised by repeatedly carrying out the following procedure from the minimum Y coordinate value Ymin to the maximum Y coordinate value Ymax.
1) If there is data related to an edge in the active-edge table, it is determined whether the edge of concern has been processed for predetermined times. When the result is affirmative, data related to this edge is deleted from the active-edge table. On the other hand, when the edge of concern has not yet been processed for the predetermined times, X=X +(.DELTA.X/.DELTA.Y) is calculated. If data related to an edge for the present Y coordinate value exists in the edge table, the data related to the present edge is transferred to the active-edge table.
2) Data stored in the active-edge table are arranged in the increasing order of X coordinate values from the smallest one of the X coordinate values in accordance with a quick sorting process.
3) Edges are extracted from the active-edge table for every two edges, and data related to a line drawn between X coordinate values of the extracted edges is generated.
However, the above-mentioned method is not suitable for filling the internal area of a polygon at high speeds for the following reasons. First, the quick sorting process used when creating the active-edge table is complex and it takes a long time. Secondly, it is necessary to change, on the basis of the state of connection of neighboring edges, the calculation procedure for determining whether each edge registered in the active-edge table has been processed for the predetermined times. For example, it is necessary to refer to the previous edge or the next edge or another edge with respect to the present edge. Therefore, it takes a long time for the calculation procedure selecting process.